package com.hardydou.algorithm;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author ：hardy
 * @description：中位数
 * @date ：Created in 2021/1/5
 * @Copyright ：Hardydou.com
 */
public class Median {

    /***
     * q1,大顶堆，存取较小的一半数据。
     * q2,小顶堆，存储较大的一半数据。
     */
    Queue<Integer> q1, q2;

    public Median() {
        this.q1 = new PriorityQueue<>();
        this.q2 = new PriorityQueue<>((x, y) -> (y - x));
    }

    public void addNum(Integer num) {
        if (q1.size() != q2.size()) {
            q1.add(num);
            q2.add(q1.poll());
        } else {
            q2.add(num);
            q1.add(q2.poll());
        }
    }

    public double findMedian() {
        double result = (q1.size() != q2.size()) ? q1.peek() : (q1.peek() + q2.peek())*1.0 / 2;
        return result;
    }

    public void status(){
        System.out.print("q1:");
        q1.forEach((x)-> System.out.print(x+","));
        System.out.print("\nq2:");
        q2.forEach((x)-> System.out.print(x+","));
        System.out.println();
    }
}
